package homework;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
 *
 * 实现 MyStack 类：
 *
 * void push(int x) 将元素 x 压入栈顶。
 * int pop() 移除并返回栈顶元素。
 * int top() 返回栈顶元素。
 * boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
 * User: LENOVO
 * Date: 2024-08-09
 * Time: 14:28
 */

//改题目要求使用队列实现栈的操作，我们可以使用两个队列来实现
    //当两个栈都是空时，即第一次执行入栈操作时，我们将其压入队列一
    //之后再压栈时候我们还是将其压入栈一，但是在执行pop出栈操作时候需要将队列一中的元素-1个都offer到队列二中
    //此时队列一中的元素就是出栈的元素，后来再进行入栈操作时，如果队列一空我们就入栈到队列一，如果队列二空我们就入栈到队列二
    //使用队列的时候我们怎么倒腾左右两个队列元素之间的上下关系也是不变的，就像我们的队列一出队后进入队列二也是第一个队首
class MyStack {
    Queue<Integer> qu1;
    Queue<Integer> qu2;
    public MyStack() {
        qu1 = new LinkedList<>();
        qu2 = new LinkedList<>();
    }

    public void push(int x) {
        if(empty()){
            qu1.offer(x);
            return;
        }
        if(! qu1.isEmpty()){
            qu1.offer(x);
        }else{
            qu2.offer(x);
        }
    }

    public int pop() {
        if(empty()){
            return -1;
        }
        if(! qu1.isEmpty()){
            if(qu1.size() == 1){
                return qu1.poll();
            }else{
                int size = qu1.size();
                while(size > 1){
                    qu2.offer(qu1.poll());
                    size--;
                }
                return qu1.poll();
            }
        }else{
            if(qu2.size() == 1){
                return qu2.poll();
            }else{
                int size = qu2.size();
                while(size > 1){
                    qu1.offer(qu2.poll());
                    size--;
                }
                return qu2.poll();
            }
        }
    }

    public int top() {
        if(empty()){
            return -1;
        }
        if(! qu1.isEmpty()){
            int size = qu1.size();
            int tmp = 0;
            while(size > 0){
                tmp = qu1.poll();
                qu2.offer(tmp);
                size--;
            }
            return tmp;
        }else {
            int size = qu2.size();
            int tmp = 0;
            while (size > 0) {
                tmp = qu2.poll();
                qu1.offer(tmp);
                size--;
            }
            return tmp;
        }
    }

    public boolean empty() {
        return qu1.isEmpty() && qu2.isEmpty();
    }
}
public class TestMyStack {
    public static void main(String[] args) {
        //"top","pop","top","pop","top","empty","pop","empty"]
        MyStack myStack = new MyStack();
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        myStack.top();//3    qu1 1 2 3
        myStack.pop();//3    qu1 3  qu2 1 2
        myStack.top();//2
        myStack.pop();//2    qu
        myStack.top();//1
        System.out.println(myStack.empty());//false
        myStack.pop();//1
        System.out.println(myStack.empty());//true
    }
}
